{
ID : phamnamlo2
PROB : lineupg
LANG : PASCAL
}

program LINEUPG;
const
  fi = 'lineupg.in';
  fo = 'lineupg.out';
  max = 50000;
  oo = 1000000000;
var
  h : array[1..max] of longint;
  smax, smin : array[1..4*max] of longint;
  n, q, a, b : longint;

procedure inp;
var
  i : longint;
begin
  read(n, q);
  for i := 1 to n do read(h[i]);
end;

function max2(x, y : longint) : longint;
begin
  if x > y then max2 := x
  else max2 := y;
end;

function min2(x, y : longint) : longint;
begin
  if x > y then min2 := y
  else min2 := x;
end;

procedure update(v, p : longint);

  procedure visit(u, l, r : longint);
  var
    mid : longint;
  begin
    if l = r then
    begin
      smin[u] := v;
      smax[u] := v;
      exit;
    end;

    mid := (l+r) shr 1;
    if p <= mid then visit(u shl 1, l, mid)
    else visit(u shl 1+1, mid+1, r);
    smin[u] := min2(smin[u shl 1], smin[u shl 1 + 1]);
    smax[u] := max2(smax[u shl 1], smax[u shl 1 + 1]);
  end;

begin
  visit(1, 1, n);
end;

function get_res(a, b : longint) : longint;
var
  mini, maxi : longint;

  procedure visit(u, l, r : longint);
  var
    mid : longint;
  begin
    if (a <= l) and (r <= b) then
    begin
      mini := min2(mini, smin[u]);
      maxi := max2(maxi, smax[u]);
      exit;
    end;

    mid := (l+r) shr 1;
    if b <= mid then visit(u shl 1, l, mid) else
    if mid+1 <= a then visit(u shl 1 + 1, mid+1, r) else
    begin
      visit(u shl 1, l, mid);
      visit(u shl 1 + 1, mid+1, r);
    end;
  end;

begin
  mini := oo;
  maxi := -1;
  visit(1, 1, n);
  get_res := maxi-mini;
end;

procedure process;
var
  i : longint;
begin
  for i := 1 to n do update(h[i], i);
  for i := 1 to q do
  begin
    read(a, b);
    writeln(get_res(a, b));
  end;
end;

begin
  assign(input, fi); reset(input);
  assign(output, fo); rewrite(output);

  inp;
  process;

  close(output);
  close(input);
end.
